
/**
 * 
 * 工作安排
 * 
 * 题目描述

小明每周上班都会拿到自己的工作清单，工作清单内包含 n 项工作，每项工作都有对应的耗时时间（单位 h）和报酬，工作的总报酬为所有已完成工作的报酬之和。

那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

输入描述
输入的第一行为两个正整数 T，n

T 代表工作时长（单位 h， 0 < T < 1000000），
n 代表工作数量（ 1 < n ≤ 3000）
接下来是 n 行，每行包含两个整数 t，w

t 代表该工作消耗的时长（单位 h， t > 0）
w 代表该项工作的报酬
输出描述
输出小明指定工作时长内工作可获得的最大报酬。

用例
输入	40 3
20 10
20 20
20 5
输出	30
说明	无

 */

import java.util.Scanner;

/**
  * 
  题目解析
本题是01背包问题。可以使用动态规划求解。关于01背包问题请先看下面这个博客

算法设计 - 01背包问题_伏城之外的博客-CSDN博客

本题中

工作时长T相当于背包承重
每一项工作相当于每件物品
工作消耗的时长相当于物品重量
工作的报酬相当于物品的价值
补充01背包的滚动数组优化，关于滚动数组优化请看算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题_01背包问题状态转移方程_伏城之外的博客-CSDN博客
  */

public class 工作安排 {
    
    public static void main(String[] args) {
        
        try{
            Scanner scanner = new Scanner(System.in);

            //工作时长
            int workotalTime = scanner.nextInt();
            //工作数量
            int workCount = scanner.nextInt();

            //遍历拿到工作信息
            int[][] workInfoAArr = new int[workCount][2];
            for(int i=0; i<workCount; i++){

                workInfoAArr[i][0] = scanner.nextInt();
                workInfoAArr[i][1] = scanner.nextInt();
            }

            int[] result = new int[workotalTime+1];
            //01背包问题滚动数组优化
            for(int n=0; n<workCount; n++){
                //工作时间
                int time = workInfoAArr[n][0];
                int money = workInfoAArr[n][0];

                //注意背包承重遍历必须倒序，正序的话就变成完全背包了
                for(int j=workotalTime; j >=time; j--){

                    result[j] = Math.max(result[j], result[j - time] + money);

                }
            }

            System.out.println(""+result[workotalTime]);


        }catch(Exception e){

            e.printStackTrace();
        }

    }
}

/**
 * 
 * 
 * 01 背包
 * 
 * 所以二维数组可以定义成：

int[][] tv = new int[4][5]
tv[i][j]就表示前i个物品，装入容量为j的背包时，能够获得的最大价值。
4怎么来的？总共有3件物品，加上没有物品的情况，就是4；5怎么来的？背包容量被我们拆成了1、2、3、4，再加上容量为0的情况，就是5。

我们再定义一个数组用来保存物品的重量：

int[] w = {1,4,3}; // 物品的重量
还需要定义一个数组来保存物品的价值：

int[] v = {15,30,20}; // 物品的价值
(1). tv[i][0] = 0，表示第一行都是0；tv[0][j] = 0，表示第一列都是0；

(2). w[i]表示的是第i件物品的重量，v[i]表示的是第i件物品的价值；j是列的索引，第0列表示背包容量为0时，第1列表示背包容量为1时，所以j表示的是当前背包的容量。

(3). 当w[i] > j时，那么就让tv[i][j] = tv[i-1][j]。也就是说，第i件物品的重量大于当前背包的容量时，那么久直接将上一行该列的那个值复制过来。

(4). 当w[i] <= j时，那么就让tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}。条件就是第i件物品的重量小于等于背包容量时，此时有两种情况，一个是装，一个是不装，怎么判断装不装呢，那就判断装能获得的总价值更大还是不装能获得的总价值更大。

如果不装第i件物品，能获得的最大价值那就和上一行该列的值一样，即tv[i-1][j]；

如果装第i件物品，能够获得的最大价值就是第i件物品的价值加上装了第i件物品后剩余容量能够获得的价值。v[i]是第i件物品的价值，怎么理解tv[i-1][j-w[i]]？首先看j-w[i]，意思就是当前背包容量减去第i件物品的重量，那也就是当前背包容量下如果装第i件物品后剩余的容量，所以tv[i-1][j-w[i]]的意思就是，去上一行找背包容量为j-w[i]时的那个值，也就是当前背包装了第i件物品后剩余容量能够获得的最大价值；v[i] + tv[i-1][j-w[i]]就是如果装第i件物品能够获得的最大价值。

经过上面的分析，tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}就很好理解了，当背包容量为j时，装前i件物品能够获得的最大价值就是在装与不装两种情况中取最大值。
 * 
 */
